import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;


class Solution {

    private final static int[][] DIR = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public int largestIsland(int[][] grid) {
        int H = grid.length, W = grid[0].length;
        int[][] islandIdxGraph = new int[H][W];
        Map<Integer, Integer> areaMap = new HashMap<>();
        int islandIdx = 1;
        for (int r = 0; r < H; r++) {
            for (int c = 0; c < W; c++) {
                if (grid[r][c] == 1 && islandIdxGraph[r][c] == 0) {
                    int area = setGraph(grid, r, c, islandIdxGraph, islandIdx);
                    areaMap.put(islandIdx, area);
                    islandIdx += 1;
                }
            }
        }

        int maxArea = 1;
        for (int r = 0; r < H; r++) {
            for (int c = 0; c < W; c++) {
                int area = 0;
                if (grid[r][c] == 0) {
                    area = 1;
                }
                Set<Integer> islandSet = new HashSet<>();
                for (int[] dir : DIR) {
                    int nextR = r + dir[0];
                    int nextC = c + dir[1];
                    if (!inBounds(grid, nextR, nextC) || grid[nextR][nextC] == 0) {
                        continue;
                    }
                    islandSet.add(islandIdxGraph[nextR][nextC]);
                }
                for (int island : islandSet) {
                    area += areaMap.get(island);
                }

                if (area > maxArea) {
                    maxArea = area;
                }
            }
        }
        return maxArea;
    }

    private boolean inBounds(int[][] grid, int r, int c) {
        int H = grid.length, W = grid[0].length;
        return r >= 0 && r < H && c >= 0 && c < W;
    }

    private int setGraph(int[][] grid, int r, int c, int[][] areaMap, int value) {
        int count = 1;
        areaMap[r][c] = value;
        for (int[] dir : DIR) {
            int nextR = r + dir[0];
            int nextC = c + dir[1];
            if (inBounds(grid, nextR, nextC) && grid[nextR][nextC] == 1 && areaMap[nextR][nextC] == 0) {
                count += setGraph(grid, nextR, nextC, areaMap, value);
            }
        }
        return count;
    }
}

public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
}